/**
 * 
 */
package leetCode;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author zhong
 *
 */
public class SumofSubsequenceWidths {
	public int sumSubseqWidthsOrder(int[] A) {
		int n = A.length;
		// 先用单调栈求出满足<=A[i]的最左侧的坐标
		int[] leftGt = new int[n];
		int[] leftLt = new int[n];
		int[] rightGt = new int[n];
		int[] rightLt = new int[n];
		for (int i = 0; i < n; i++) {
			leftGt[i] = -1;
			leftLt[i] = -1;
			rightGt[i] = n;
			rightLt[i] = n;
		}
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < A.length; i++) {
			while (!stack.isEmpty() && A[stack.peek()] < A[i]) {
				int j = stack.pop();
				rightGt[j] = i;// j右侧第一个比A[j]大的坐标
				leftLt[i] = Math.max(j, leftLt[i]);// i左侧第一个比A[i]小的
			}
			stack.push(i);
		}
		stack.clear();
		for (int i = 0; i < A.length; i++) {
			while (!stack.isEmpty() && A[stack.peek()] > A[i]) {
				int j = stack.pop();
				rightLt[j] = i;// j右侧第一个比A[j]小的坐标
				leftGt[i] = Math.max(j, leftLt[i]);// i左侧第一个比A[i]大的
			}
			stack.push(i);
		}
		int sum = 0;
		int mod = 1000000007;
		for (int i = 0; i < n; i++) {
			int gt = rightGt[i] - leftGt[i] - 1;
			int lt = rightLt[i] - leftLt[i] - 1;
			int times = gt * gt - lt * lt;
			sum += times * A[i] % mod;
			if (sum < 0) {
				sum += mod;
			}
			sum %= mod;
		}
		return sum;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A = { 2, 1 };
		System.out.println(new SumofSubsequenceWidths().sumSubseqWidths(A));
	}

	public int sumSubseqWidths(int[] A) {
		int n = A.length;
		Arrays.sort(A);
		int sum = 0;
		int mod = 1000000007;
		int i = 0;
		while (i < n) {
			// 找到>A[i]的个数和小于A[i]的个数
			int lessCnt = i;
			int val = A[i];
			int equalCnt = 1;
			i++;
			while (i < n && A[i] == val) {
				i++;
				equalCnt++;
			}
			int greaterCnt = n - i - equalCnt + 1;
			sum += val * (getRes(mod, 2, lessCnt) - getRes(mod, 2, greaterCnt)) % mod * equalCnt % mod;
			sum %= mod;
		}
		return sum;
	}

	private int getRes(int mod, int base, int exp) {
		double res = 1;
		for (int i = 0; i < exp; i++) {
			res *= exp;
			res %= mod;
		}
		return (int) res;
	}

}
